package Solution.problem079.WordSearch;

import org.junit.Test;

/**
 * @program Leetcode
 * @description:
 *
 *深度有限遍历
 *
 * Given a 2D board and a word, find if the word exists in the grid.
 *
 * The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
 *
 * For example,
 * Given board =
 *
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 * word = "ABCCED", -> returns true,
 * word = "SEE", -> returns true,
 * word = "ABCB", -> returns false.



必然要对每一点的每一条路径进行深度遍历，遍历过程中一旦出现：
1.数组越界、
2.该点已访问过、
3.该点的字符和word对应的index字符不匹配！

 * @author: lishangsheng
 * @create: 2019/06/15 11:40
 */
public class Solution {
    public boolean exist(char[][] board, String word) {
        /** 一个个点的开始深度遍历*/
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, int i, int j, String word, int index) {
        /** 深度遍历代码核心*/
        if (index > word.length() - 1) {
            /** 单词的字母全找到了*/
            return true;
        }

        if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) {
            /** 数组下标越界了，已经不在数组内了，结束这次遍历*/
            return false;
        }
        if (board[i][j] != word.charAt(index)) {
            /** 该路径不对，返回false*/
            return false;
        }

        char temp = board[i][j];
        board[i][j] = '$';

        /** 前后左右的遍历，有一个路径是通的就返回true*/
        boolean result = (dfs(board, i + 1, j, word, index + 1) ||
                dfs(board, i - 1, j, word, index + 1) ||
                dfs(board, i, j + 1, word, index + 1) ||
                dfs(board, i, j - 1, word, index + 1));
        board[i][j] = temp;
        return result;

    }

    @Test
    public void test(){

    }
}
